package com.leetcode.算法策略相关.递归;

/**
 * @author: ZhouBert
 * @date: 2021/3/2
 * @description: 1137. 第 N 个泰波那契数
 * https://leetcode-cn.com/problems/n-th-tribonacci-number/
 */
public class A_1137_第N个泰波那契数 {

	static A_1137_第N个泰波那契数 action = new A_1137_第N个泰波那契数();

	public static void main(String[] args) {
		//test1();
		test2();
	}

	public static void test1() {
		int res = action.tribonacciByRecursiveArrUp(25);
		System.out.println("res = " + res);
	}

	public static void test2() {
		int res = action.tribonacciByRecursiveArrUp(35);
		System.out.println("res = " + res);
	}


	/**
	 * 这样的递归时间很长的，那么可以使用数组进行优化
	 *
	 * @param n
	 * @return
	 */
	public int tribonacciBySimpleRecursive(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		return tribonacciBySimpleRecursive(n - 1) + tribonacciBySimpleRecursive(n - 2)
				+ tribonacciBySimpleRecursive(n - 3);
	}

	/**
	 * 避免重复计算的好办法
	 */
	int[] arr;

	/**
	 * 使用一个数组来保存中间计算的值避免重复计算
	 * 卧槽这也能超时？
	 *
	 * @param n
	 * @return
	 */
	public int tribonacciByRecursiveArrUp(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		arr = new int[n + 1];
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 1;
		return tribonacciByArrUp(n);
	}

	private int tribonacciByArrUp(int n) {
		if (n == 0) {
			return 0;
		}
		if (arr[n] != 0) {
			return arr[n];
		}

		int value = tribonacciByArrUp(n - 1) + tribonacciByArrUp(n - 2) +
				tribonacciByArrUp(n - 3);
		arr[n] = value;
		return value;
	}
}
